문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 P-NP 문제 (문단 편집) === [[알고리즘]]의 [[시간 복잡도]] === 컴퓨터를 이용해 특정한 계산 문제를 풀기 위해서는 그 문제에 해당되는 알고리즘을 컴퓨터에게 알려주어야 한다. 하지만 충분히 짧은 시간 안에 작동하지 않는 비효율적인 알고리즘은 실용성이 없을뿐더러 어떠한 학문적 흥미도 끌지 못한다. 따라서 컴퓨터과학자들의 주된 관심사는 알고리즘이 특정 문제를 얼마나 빨리 해결할 수 있느냐는 것이다. 물론 알고리즘에 입력한 자료의 크기가 커질수록 일반적으로 알고리즘의 수행 시간은 점점 오래 걸린다. 예를 들어 어떤 컴퓨터가 숫자 100개를 더하는 문제를 푸는 데 100 나노초가 걸렸다면, 이 컴퓨터가 숫자 1000개를 더하는 문제를 풀 때는 1000 나노초가 소요될 것임을 어렵지 않게 짐작할 수 있다. 보다 일반적으로 말해서, [math(n)]자리의 두 수를 더하는 데에는 약 [math(n)] 나노초가 소요될 것이다. 컴퓨터과학에서는 알고리즘의 시간복잡도를 [math(\mathcal{O}(n))]이라고 표기하는데, [[점근 표기법|[math(\mathcal{O})]라는 표시]]는 간단히 말해 [math(n)] 앞에 곱해질 비례상수는 신경 쓰지 않겠다는 의미다. 어떤 문제가 [math(\mathcal{O}(n))] 알고리즘을 가진다는 것은 그 문제가 컴퓨터에게 아주 쉬운 문제라는 것을 의미한다. 조금 더 복잡한 문제를 생각해보자. 만약 [math(n)]자리의 두 자연수를 곱해야 한다면 얼마나 많은 계산이 필요할까? 컴퓨터 없이 손으로 이를 푼다고 가정해보면, 그 중간 과정에서는 [math(n)]개의 행이 필요할 것이고, 각각의 행은 다시 [math(n)]개의 숫자로 구성되어 있을 것이다. 그러므로 [math(n)]자리의 두 자연수를 곱하는 문제를 손으로 푸는 건 거의 [math(n^2)]에 비례하는 시간이 필요하다. 이때는 알고리즘의 시간복잡도가 [math(\mathcal{O}(n^2))]가 된다. 즉, 100자리 수의 곱셈을 하는 것은 10자리 수의 곱셈을 하는 것보다 10배가 아닌 100배나 어려운 문제라는 것이다. 따라서 곱셈은 덧셈보다는 비교적 어려운 문제라는 결론을 도출할 수 있다. 만약 대소문자 구별 없는 a~z까지의 로마자 알파벳(26가지)을 무작위로 골라 만든 10자리의 비밀번호를, 모든 가능성을 다 대입해봄([[브루트 포스]])으로써 알아내고자 한다면 얼마나 많은 시도가 필요할까? 잘 알다시피 최대 [math(26^{10})], 즉 약 141조 번에 달하는 수많은 시도가 필요하다. 하지만 현대의 [[슈퍼컴퓨터]]를 동원하면 이 정도의 작업은 가능한 일의 범위 안에 있다. 그렇다면 상황을 더욱 극단적으로 만들어서, 100자리의 비밀번호를 이러한 방식으로 풀려면 얼마나 많은 시도가 필요할까? [math(26^{100})]은 10의 112제곱인 [[긍갈라]]보다도 몇십 [[양(수)|양]]배나 큰 수[* 대략 [math(3.1429\times10^{141})] 정도. 정확한 값은 3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376]다. 이때의 시간복잡도는 [math(\mathcal{O}(26^n))]으로, 이 문제는 [math(n)]자리 수의 곱셈과는 차원이 다른, 규모를 헤아리기조차 힘들 만큼 어마어마하게 어려운 문제임을 알 수 있다. 앞의 쉬운 문제 두 개와 뒤의 어려운 문제의 차이점은 간단하다. 앞의 문제들에 대한 알고리즘은 [math(\mathcal{O})]의 괄호 안에 들어있는 식이 [math(n)]에 대한 '다항식'이었고, 뒤의 어마어마하게 어려운 문제는 [math(\mathcal{O})]의 괄호 안에 [math(n)]에 대한 '지수함수'가 들어 있다는 것이 중요한 차이점이다. 물론 다항식도 [math(n)]이 커지면 값이 증가하지만 그것은 지수함수의 것에 비하면 새 발의 피에 불과하다. 다시 말해 다항식 시간 알고리즘이 존재하는 문제는 고성능 컴퓨터를 통하면 비교적 원활히 해결할 수 있는 쉬운(tractable) 문제고, 다항식 시간 알고리즘이 존재하지 않는 문제는 온 우주가 힘을 모아도 푸는 게 불가능할 수 있는 어려운(intractable) 문제다. 이를 통해 우리는 어떤 문제가 쉬운지 어려운지를 판별할 수 있다. 다행히도 수학/과학적으로 중요한 많은 문제들이 다항식 시간 알고리즘을 가지는 것으로 확인되었다. [math(n)]개의 숫자를 입력받고, 그들을 크기순으로 정렬하는 [[정렬]] 문제가 대표적이다. 그 외에도 어떤 도로망의 지도가 주어졌을 때, 주어진 출발지와 목적지 사이의 최단 경로를 찾아내는 문제([[다익스트라 알고리즘]])도 다항식 시간에 풀 수 있다. 그러나 어떤 [math(n)]자리 자연수를 소인수분해하는 다항식 시간 알고리즘은 아직까지 아무도 찾아내지 못했다. 서로 다른 두 문제의 난이도를 비교하는 데에는 환원(reduction)이라는 기법이 자주 사용된다. 예를 들어, 다음 두 가지 문제를 보자. >문제 A: 주어진 [math(n)]개의 숫자를 크기 순서로 정렬하는 문제 >문제 B: 주어진 [math(n)]개 숫자의 중앙값을 계산하는 문제 어떤 사람이 문제 A를 쉽게 풀 수 있다면, 그 사람은 문제 B도 쉽게 풀 수 있다는 걸 직관적으로 알 수 있을 것이다. 다시 말해, 문제 B의 난이도는 문제 A의 난이도보다 어려울 수 없다. 주어진 숫자들이 정렬됐다면, 그중 정가운데에 있는 수를 뽑기만 해도 문제 B가 해결되기 때문이다. 이를 "문제 B를 문제 A로 환원시킬 수 있다"고 표현한다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기